class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int m = heightMap.size(), n = heightMap[0].size();
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
        vector<vector<bool>> w(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    w[i][j] = true;
                    pq.push({ heightMap[i][j], i, j });
                }

        int ret = 0;
        int dx[4] = { 0, 0, 1, -1 };
        int dy[4] = { 1, -1, 0, 0 };
        while (pq.size()) {
            auto a = pq.top();
            pq.pop();
            int x = get<1>(a), y = get<2>(a);
            for (int k = 0; k < 4; k++) {
                int xa = x + dx[k], ya = y + dy[k];
                if (xa > 0 && ya > 0 && xa < m && ya < n && !w[xa][ya]) {
                    if (heightMap[xa][ya] < heightMap[x][y]) {
                        ret += heightMap[x][y] - heightMap[xa][ya], heightMap[xa][ya] = heightMap[x][y];
                    }
                    w[xa][ya] = true;
                    pq.push({ heightMap[xa][ya], xa, ya });
                }
            }
        }
        return ret;
    }
};